/**
 * 273. 整数转换英文表示
 * https://leetcode-cn.com/problems/integer-to-english-words/
 */
public class Solutions_273 {
    public static void main(String[] args) {
//        int num = 123;  // output: "One Hundred Twenty Three"
//        int num = 12345;  // output: "Twelve Thousand Three Hundred Forty Five"
//        int num = 1234567;  // output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
        int num = 1234567891;  // output: "One Billion Two Hundred Thirty Four Million Five Hundred
                                            // Sixty Seven Thousand Eight Hundred Ninety One"
//        int num = Integer.MAX_VALUE;  // output: "Two Billion One Hundred Forty Seven Million Four Hundred
                                            // Eighty Three Thousand Six Hundred Forty Seven"  2147483647

        String result = numberToWords(num);
        System.out.println(result);
    }


    // one[2] = 2：数值的字符串表示
    private static final String[] one = {"Zero", "One", "Two", "Three", "Four", "Five", "Six",
            "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
            "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    // ten[2] = 2 * 10 = 20：数值的字符串表示
    private static final String[] ten = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty",
            "Sixty", "Seventy", "Eighty", "Ninety"};

    /**
     * 解法二：分治法 + 哈希表方式（1ms）
     */
    public static String numberToWords(int num) {
        if (num == 0) {
            return one[0];
        }
        StringBuilder sb = new StringBuilder();
        if (num / 1_000_000_000 > 0) {
            // 取十亿位
            sb.append(one[num / 1_000_000_000]);
            sb.append(" Billion");
            num = num % 1_000_000_000;
        }
        if (num / 1_000_000 > 0) {
            // 取百万位（亿、千万、百万）
            getThree(num / 1_000_000, sb);
            sb.append(" Million");
            num = num % 1_000_000;
        }
        if (num / 1000 > 0) {
            // 取千位（十万、万、千）
            getThree(num / 1000, sb);
            sb.append(" Thousand");
            num = num % 1000;
        }
        if (num > 0) {
            // 取个位（百、十、个）
            getThree(num, sb);
        }
        return sb.toString();
    }

    /**
     * 对分割的三位进行字符串转换
     */
    public static void getThree(int num, StringBuilder sb) {
        if (num / 100 > 0) {
            // 取百位
            if (sb.length() > 0) {
                sb.append(" ");
            }
            sb.append(one[num / 100]);
            sb.append(" Hundred");
            num = num % 100;
        }
        if (num == 0) {
            // 十位和个位没有数字
            return;
        }
        // 取十位
        if (num < 20) {
            // 可直接取值的情况：10，11，12，13...19
            if (sb.length() > 0) {
                sb.append(" ");
            }
            sb.append(one[num]);
        } else {
            // [20, 99] 的情况，需要十位 + 个位分别转换字符串
            if (sb.length() > 0) {
                sb.append(" ");
            }
            // 十位转换
            sb.append(ten[num / 10]);
            num = num % 10;
            if (num > 0) {
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                // 个位转换
                sb.append(one[num]);
            }
        }
    }



    public static String one(int num) {
        // 个数上的一位数，转字符串
        switch(num) {
            case 1: return "One";
            case 2: return "Two";
            case 3: return "Three";
            case 4: return "Four";
            case 5: return "Five";
            case 6: return "Six";
            case 7: return "Seven";
            case 8: return "Eight";
            case 9: return "Nine";
        }
        return "";
    }

    public static String ten(int num) {
        // 十位上的一位数，转字符串
        switch(num) {
            case 2: return "Twenty";
            case 3: return "Thirty";
            case 4: return "Forty";
            case 5: return "Fifty";
            case 6: return "Sixty";
            case 7: return "Seventy";
            case 8: return "Eighty";
            case 9: return "Ninety";
        }
        return "";
    }

    public static String twoLessThan20(int num) {
        // [10, 19] 之间的数字，转字符串
        switch(num) {
            case 10: return "Ten";
            case 11: return "Eleven";
            case 12: return "Twelve";
            case 13: return "Thirteen";
            case 14: return "Fourteen";
            case 15: return "Fifteen";
            case 16: return "Sixteen";
            case 17: return "Seventeen";
            case 18: return "Eighteen";
            case 19: return "Nineteen";
        }
        return "";
    }

    public static String two(int num) {
        // 两位数，转字符串
        if (num == 0) {
            return "";
        } else if (num < 10) {
            // 1，2，3，4，5，...9 的情况，仅有一位，十位是 0
            return one(num);
        } else if (num < 20) {
            // 10，11，12，13，14，15... 19 的情况，有独立的单词
            return twoLessThan20(num);
        } else {
            // 20，21，31，45，60，99 的情况
            // 获取十位，个位
            int tenner = num / 10;
            int rest = num % 10;
            if (rest == 0) {
                // 没有个位
                return ten(tenner);
            } else {
                // 有十位、有个位
                return ten(tenner) + " " + one(rest);
            }
        }
    }

    public static String three(int num) {
        // 三位数，转字符串
        int hundred = num / 100;
        String res = "";
        int rest = num % 100;
        if (hundred != 0) {
            if (rest != 0) {
                // 既有百位，又有十位或者个位
                res = one(hundred) + " Hundred " + two(rest);
            } else {
                // 仅有百位
                res = one(hundred) + " Hundred";
            }
        } else {
            // 没有百位
            res = two(rest);
        }
        return res;
    }

    /**
     * 解法一：分治法（12ms）
     */
    public static String numberToWords2(int num) {
        // 所有的整数，都可以分解为三位三位一组
        if (num == 0) {
            return "Zero";
        }
        // 单位：十亿
        int billion = num / 1000_000_000;
        // 单位：百万
        int million = (num % 1000_000_000) / 1_000_000;
        // 单位：千
        int thousand = (num % 1000_000) / 1000;
        // 低三位的值
        int rest = num % 1000;

        String result = "";
        if (billion != 0) {
            result = three(billion) + " Billion";
        }
        if (million != 0) {
            if (result.length() > 0) {
                result += " ";
            }
            result += three(million) + " Million";
        }
        if (thousand != 0) {
            if (result.length() > 0) {
                result += " ";
            }
            result += three(thousand) + " Thousand";
        }
        if (rest != 0) {
            if (result.length() > 1) {
                result += " ";
            }
            result += three(rest);
        }
        return result;
    }
}
